๋ฌธ์
Programmers - ์์ดํ ์ค๊ธฐ
๐ Logic
// ์ฃผ์ด์ง ์ฌ๊ฐํ ์ ๋ณด๋ฅผ ์ด์ฉํด ํ
๋๋ฆฌ์ ๋ด๋ถ ์ ๋ณด๋ฅผ map์ ํ์
private void fillMap(int[] rect) {
int x1 = rect[0] * 2;
int y1 = rect[1] * 2;
int x2 = rect[2] * 2;
int y2 = rect[3] * 2;
// ๋ด๋ถ ์์น
// -1 : ๋ด๋ถ
// 1 : ํ
๋๋ฆฌ
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
if (map[i][j] == -1) continue;
map[i][j] = -1;
if (i == x1 || i == x2 || j == y1 || j == y2) map[i][j] = 1;
}
}
}
- ์ฃผ์ด์ง ์ฌ๊ฐํ ์ขํ๋ฅผ 2๋ฐฐํ์ฌ ์ ์ฅํ๋ค.
ใท์ํ ๋ง๋ฌ์ ๋ ์ ํํ์ง ์๋๋ก ํ๊ธฐ ์ํจ์ด๋ค...
private void bfs(int cX, int cY, int iX, int iY) {
int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
boolean[][] visited = new boolean[101][101];
Queue<Coor> queue = new LinkedList<>();
queue.add(new Coor(cX, cY));
while(!queue.isEmpty()) {
Coor c = queue.poll();
int curX = c.x;
int curY = c.y;
for (int[] d : dir) {
int nX = curX + d[0];
int nY = curY + d[1];
if (!isValid(nX, nY)) continue;
if (map[nX][nY] != 1 || visited[nX][nY]) continue;
// map์ ๋น์ฉ ์ ์ฅ
map[nX][nY] = map[curX][curY] + 1;
if (nX == iX && nY == iY) {
// ์ด๋ฏธ ์ ์ฅ๋ ๊ฐ์ด ์๋ค๋ฉด, ๋ ์ต์ ๊ฐ์ ์ ์ฅ
answer = Math.min(answer, map[nX][nY]);
continue;
}
visited[nX][nY] = true;
queue.add(new Coor(nX, nY));
}
}
}
- ๊ทธ์ BFS, ๋ค๋ง ํ ๋๋ฆฌ์ธ ๋ ์๋ค๋ง ๊ณจ๋ผ ํ์ํ๋ค. ์์ดํ ์ ์ฃผ์๋ ๋ ๋นจ๋ฆฌ ๊ฐ๋ ๋ฐฉ๋ฒ์ด ์์ ์ ์์ผ๋ ๊ณ์ ํ์ํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Coor {
int x;
int y;
public Coor(int x, int y) {
this.x = x;
this.y = y;
}
}
class Solution {
private static int[][] map = new int[101][101];
private static int answer = Integer.MAX_VALUE;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
for (int[] rect : rectangle)
fillMap(rect);
bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
return answer/2;
}
// ์ฃผ์ด์ง ์ฌ๊ฐํ ์ ๋ณด๋ฅผ ์ด์ฉํด ํ
๋๋ฆฌ์ ๋ด๋ถ ์ ๋ณด๋ฅผ map์ ํ์
private void fillMap(int[] rect) {
int x1 = rect[0] * 2;
int y1 = rect[1] * 2;
int x2 = rect[2] * 2;
int y2 = rect[3] * 2;
// ๋ด๋ถ ์์น
// -1 : ๋ด๋ถ
// 1 : ํ
๋๋ฆฌ
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
if (map[i][j] == -1) continue;
map[i][j] = -1;
if (i == x1 || i == x2 || j == y1 || j == y2) map[i][j] = 1;
}
}
}
private void bfs(int cX, int cY, int iX, int iY) {
int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
boolean[][] visited = new boolean[101][101];
Queue<Coor> queue = new LinkedList<>();
queue.add(new Coor(cX, cY));
while(!queue.isEmpty()) {
Coor c = queue.poll();
int curX = c.x;
int curY = c.y;
for (int[] d : dir) {
int nX = curX + d[0];
int nY = curY + d[1];
if (!isValid(nX, nY)) continue;
if (map[nX][nY] != 1 || visited[nX][nY]) continue;
// map์ ๋น์ฉ ์ ์ฅ
map[nX][nY] = map[curX][curY] + 1;
if (nX == iX && nY == iY) {
// ์ด๋ฏธ ์ ์ฅ๋ ๊ฐ์ด ์๋ค๋ฉด, ๋ ์ต์ ๊ฐ์ ์ ์ฅ
answer = Math.min(answer, map[nX][nY]);
continue;
}
visited[nX][nY] = true;
queue.add(new Coor(nX, nY));
}
}
}
private boolean isValid(int i, int j) {
return i >= 0 && i < 101 && j >= 0 && j < 101;
}
}
โ๏ธ Review
-
์ฒ์์๋ ํฐ
map์ ๊ฐ ์ง์ฌ๊ฐํ ์ขํ๋ค์ ์ถ๊ฐํ๋ฉด์, ํ ๋๋ฆฌ๋1, ๋ด๋ถ๋-1๋ก ํํํ์ฌ ์ ์ฒด ํ ๋๋ฆฌ๋ ๊ฒฐ๊ตญ1๋ก๋ง ์ด๋ฃจ์ด์ง๊ฒ ํ๋ค. ์ดํ1์ธ ์ขํ๋ค์ ๋ฐ๋ผ๊ฐ๊ฒ ํ๋๋ฐ, ๋ฐ๋ก๋ก ์ธํด ์๋ชป๋จ์ ์์๋ค.- ์ฌ์ค 2๋ฐฐ๋ก ํ์ฅํ๋ค๋ ํ์ด๋ฅผ ์ผํ ๋ดค์ง๋ง ์๋ฌด๋ฆฌ ์๊ฐํด๋ ๋ ํจ์จ์ ์ผ๋ก ์งค ์ ์์ ๊ฒ ๊ฐ์์ ํ
๋๋ฆฌ๋ง๋ค์ ๋ฐฉํฅ์ ์ ์ฅํ๊ณ ํ์ ์์ ์ฌ์ฉํ๋ ๋ฐฉ๋ฒ๋ ์๊ฐํ์ง๋ง ๊ฐ๋งํ ์๊ฐํด๋ณด๋
ใทํํ์์ ๋ฌด์กฐ๊ฑด ๋ชฉํ๋๋ก ๋์ํ์ง ์์ ๊ฒ ๊ฐ์๋ค.
- ์ฌ์ค 2๋ฐฐ๋ก ํ์ฅํ๋ค๋ ํ์ด๋ฅผ ์ผํ ๋ดค์ง๋ง ์๋ฌด๋ฆฌ ์๊ฐํด๋ ๋ ํจ์จ์ ์ผ๋ก ์งค ์ ์์ ๊ฒ ๊ฐ์์ ํ
๋๋ฆฌ๋ง๋ค์ ๋ฐฉํฅ์ ์ ์ฅํ๊ณ ํ์ ์์ ์ฌ์ฉํ๋ ๋ฐฉ๋ฒ๋ ์๊ฐํ์ง๋ง ๊ฐ๋งํ ์๊ฐํด๋ณด๋
- ๊ทธ๋ฅ ์ก๋ค. ๋ฉ์ฒญ์ด